import java.util.ArrayList;
import java.util.Random;

import model.SimpleStringOrganism;
import model.SimpleStringOrganismFactory;


public class Main {
	
	private static int NUMBER_ORGANISMS = 100;
	private static String modelString = "The quick brown";
	private static int NUMBER_GENES = modelString.length();	
	private static int ALLELES = 130; 		//This is the range of random characters for each organism (ascii letters go up to 122)
	private static double MUTATION_RATE = 0.001;
	private static int MAX_FITNESS = NUMBER_GENES;
	
	private static Random random = new Random(0);
	//private static Random random = new Random(System.currentTimeMillis());
	
	private static ArrayList<SimpleStringOrganism> currentGeneration = new ArrayList<SimpleStringOrganism>(NUMBER_ORGANISMS);
	private static ArrayList<SimpleStringOrganism> nextGeneration = new ArrayList<SimpleStringOrganism>(NUMBER_ORGANISMS);
	private static SimpleStringOrganism modelOrganism = SimpleStringOrganismFactory.createOrganismWithChromosones("Hello world!");
	private static int [] organismFitnesses = new int[NUMBER_ORGANISMS];
	private static int totalGenerationFitness;
	
	public static void main(String[] args) {	
		int finalGeneration;

		finalGeneration = doOneRun();
		System.out.println("The evolution took " + finalGeneration +" generations");
	}

	private static int doOneRun(){

		int generations = 1;						//count of generations passed
		boolean perfectGeneration = false;			//true when the solution is reached
	
		initializeOrganisms();
		while(generations < 1000000){
			perfectGeneration = evaluateOrganisms();
			if(perfectGeneration) return generations;
			produceNextGeneration();
			generations++;
		}
		System.out.println("Looped through 100,000 generations without a perfect match :(");
		return 100001;
	}

	private static void initializeOrganisms(){
		int organismIndex;
		int gene;

		//initialize normal organisms
		for(organismIndex = 0; organismIndex < NUMBER_ORGANISMS; organismIndex++){
			for(gene = 0; gene < NUMBER_GENES; gene++){
				SimpleStringOrganism simpleStringOrganism = currentGeneration.get(organismIndex);
				Character c = new Character((char)(Math.abs(random.nextInt())%ALLELES));
				simpleStringOrganism.setChromosoneAtIndex(gene,c);
			}
		}
	}

	private static boolean evaluateOrganisms()
	{
		int organism;							
		int gene;								
		int currentOrganismFitness;				
		int bestOrganismFitness = 0;			
		char[] bestOrganism = new char[NUMBER_GENES];		

		totalGenerationFitness = 0;

		for(organism = 0; organism < NUMBER_ORGANISMS; organism++){
			currentOrganismFitness = 0;

			//tally up number of correct items in current organism
			for(gene = 0; gene < NUMBER_GENES; gene++){
				if(currentGeneration[organism][gene] == modelOrganism[gene]) currentOrganismFitness++;
			}

			//check if this organism is better than the current best
			if(currentOrganismFitness > bestOrganismFitness){
				bestOrganismFitness = currentOrganismFitness;
				for(gene = 0; gene < NUMBER_GENES; gene ++){
					bestOrganism[gene] = currentGeneration[organism][gene];
				}
			}
			//add the organisms fitness to the organismsFitnesses array and add up the generations total fitness
			organismFitnesses[organism] = currentOrganismFitness;
			totalGenerationFitness += currentOrganismFitness;

			//check for perfect match to model organism
			if(currentOrganismFitness == MAX_FITNESS) {
				return true;
			}
		}
		printGenerationToFile();
		for(gene = 0; gene < NUMBER_GENES; gene++) System.out.print(bestOrganism[gene]);
		System.out.println("  -  Organism Fitness: " + bestOrganismFitness);
		return false;
	}

	private static void printGenerationToFile() {
		
	}

	static void produceNextGeneration(){
		int organism;
		int gene;
		int parentOne;
		int parentTwo;
		int crossoverPoint;
		int mutateThisGene;

		//create children organisms in nextGeneration array
		for(organism = 0; organism < NUMBER_ORGANISMS; organism++){
			parentOne = selectOneOrganism();
			parentTwo = selectOneOrganism();
			if(parentOne == -1 || parentTwo == -1) System.out.println("One of the parents is not a real organism");

			crossoverPoint = Math.abs(random.nextInt()%NUMBER_GENES);

			for(gene = 0; gene < NUMBER_GENES; gene++){

				//single gene mutation
				mutateThisGene = Math.abs(random.nextInt()) % (int)(1.0/MUTATION_RATE);
				if(mutateThisGene == 0) nextGeneration[organism][gene] = (char) (Math.abs(random.nextInt())%ALLELES);
				else{
					if(gene < crossoverPoint) nextGeneration[organism][gene] = currentGeneration[parentOne][gene];
					else nextGeneration[organism][gene] = currentGeneration[parentTwo][gene];
				}
			}
		}
		//copy children from NextGeneration array back into currentGeneration (kill off old generation)
		for(organism = 0; organism < NUMBER_ORGANISMS; organism++){
			for(gene = 0; gene < NUMBER_GENES; gene++){
				currentGeneration[organism][gene] = nextGeneration[organism][gene];
			}
		}
	}

	static int selectOneOrganism(){
		int organism;
		int runningTotal;
		int randomSelectPoint;

		runningTotal = 0;
		randomSelectPoint = Math.abs(random.nextInt())%(totalGenerationFitness + 1);

		//count up until randomSelectPoint is reached, and take the organism at that point
		//this allows organisms with higher fitness to have a better chance of being selected
		for(organism = 0; organism < NUMBER_ORGANISMS; organism++){
			runningTotal += organismFitnesses[organism];
			if(runningTotal >= randomSelectPoint) return organism;
		}
		return -1;
	}
}
